package com.hsp.learn.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @Author Zan
 * @Create 2024/9/23 10:58
 * @ClassName: PolandNotation
 * @Description : 逆波兰计算器分析和实现
 */
public class PolandNotation {
    public static void main(String[] args) {
        // 将中缀表达式转换成后缀表达式
        // 1. 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
        // 2. 因为直接对一个字符串进行操作，不方便，因此先将字符串转换成List（中缀表达式对应的List）
        //    即 "1+((2+3)*4)-5" => ArrayList[1, +, (, (, 2, +, 3, ......]
        // 3. 将得到的中缀表达式对应的List => 后缀表达式对应的List
        //    即 ArrayList[1, +, (, (, 2, +, 3, ......] => ArrayList[1, 2, 3, +, 4, *, +, 5, -]
        String expression = "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println(infixExpressionList);

        List<String> list = parseSuffixExpressionList(infixExpressionList);
        System.out.println(list);

        int calculate = calculate(list);
        System.out.println(calculate);

        // 先定义一个逆波兰表达式
        // (3+4)*5-6 => 3 4 + 5 * 6 -
        // 4*5-8+60+8/2 => 76 => 4 5 * 8 - 60 + 8 2 / +
        // 为了方便，逆波兰表达式的数字和符号使用空格隔开
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
        // 思路
        // 1. 先将 suffixExpression 放到ArrayList中
        // 2. 将 ArrayList 传递给一个方法，遍历ArrayList 配合栈 完成计算
        List<String> listString = getListString(suffixExpression);
        System.out.println(listString);

        int res = calculate(listString);
        System.out.println(res);
    }

    // 即 ArrayList[1, +, (, (, 2, +, 3, ......] => ArrayList[1, 2, 3, +, 4, *, +, 5, -]
    // 方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
    public static List<String> parseSuffixExpressionList(List<String> list) {
        // 定义两个栈
        Stack<String> s1 = new Stack<>(); // 符号栈
        // 说明，因为s2这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
        // 因此比较麻烦，因此我们就不用栈了，直接使用List<String>的结构来替代
//        Stack<String> s2 = new Stack<>(); // 存储中间结果的栈
        List<String> s2 = new ArrayList<>();

        // 遍历list
        for (String item : list) {
            // 如果是数字，就加入到s2
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.add(item);
            } else if (item.equals(")")) {
                // 如果是右括号")"，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop(); // 丢弃括号，将左括号弹出，消除小括号
            } else {
                // 遇到运算符
                // 当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入s2，再次转到(4-1)与s1中新的栈顶运算符相比较
                while (!s1.isEmpty() && (Operation.getValue(item) <= Operation.getValue(s1.peek()))) {
                    s2.add(s1.pop());
                }
                // 把当前扫描到的运算符压入进去
                s1.push(item);
            }
        }

        // 将s1中剩余的运算符依次弹出并压入到s2
        while (!s1.isEmpty()) {
            s2.add(s1.pop());
        }

        return s2; // 因为是存放到一个list中，因此按顺序输出就是对应的逆波兰表达式（后缀表达式）
    }

    // 方法：将中缀表达式转成对应的List
    public static List<String> toInfixExpressionList(String s) {
        // 定义一个List，存放中缀表达式对应的内容
        List<String> list = new ArrayList<>();
        int i = 0; // 这是一个指针，用于遍历中缀表达式字符串
        String str; // 对多位数的拼接
        char c; // 每遍历到一个字符就放入到c中
        do {
            // 如果c是一个非数字，就需要加入到list中
            if (((c = s.charAt(i)) < 48) || ((c = s.charAt(i)) > 57)) {
                list.add("" + c);
                i++; // i 需要后移
            } else { // 如果是一个数，需要考虑多位数的问题
                str = ""; // 先将str置成空串，'0'[48] -> '9'[57]
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c; // 拼接
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;
    }

    // 将逆波兰表达式依次将数字和运算符放入到一个ArrayList中
    public static List<String> getListString(String suffixExpression) {
        // split 将 suffixExpression 分割
        return new ArrayList<>(Arrays.asList(suffixExpression.split(" ")));
    }

    // 完成对逆波兰表达式的运算
    /**
     * （1）从左至右扫描，将3和4压入堆栈
     * （2）遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈
     * （3）将5入栈
     * （4）接下来是*运算符，因此弹出5和7，计算出7*5=35，将35入栈
     * （5）将6入栈
     * （6）最后是运算符，计算出35-6的值，即29，由此得出最后结果
     */
    public static int calculate(List<String> list) {
        // 创建给栈，只需要一个栈即可
        Stack<String> stack = new Stack<>();
        // 遍历 list
        for (String item : list) {
            // 使用正则表达式来取出数
            if (item.matches("\\d+")) { // 匹配的是多位数
                // 入栈
                stack.push(item);
            } else {
                // pop 出两个数，并运算，再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop()); // 后面那个数
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                // 把res入栈
                stack.push("" + res);
            }
        }
        // 最后留在stack中的数据就是运算结果
        return Integer.parseInt(stack.pop());
    }
}

// 编写一个类 Operation 可以返回一个运算符对应的优先级
class Operation {

    private final static int ADD = 1;

    private final static int SUB = 2;

    private final static int MUL = 3;

    private final static int DIV = 4;

    // 写一个方法，返回对应的优先级数字
    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符");
                break;
        }
        return result;
    }
}